function RunTable(){
    this._runs = [];
    this._table = [];
}
(function (){
    var _RUN_ZERO = 0;
    var _RUN_CHAR = 1;
    var _RUN_CJK_CHAR = 2;
    var _RUN_TAB = 4;
    var _RUN_EOF = -1;
    RunTable.prototype = {
        tabSize: 4,
        _regex: /([\t]+)|([\u1100-\u115F\u11A3-\u11A7\u11FA-\u11FF\u2329-\u232A\u2E80-\u2E99\u2E9B-\u2EF3\u2F00-\u2FD5\u2FF0-\u2FFB\u3000-\u303E\u3041-\u3096\u3099-\u30FF\u3105-\u312D\u3131-\u318E\u3190-\u31BA\u31C0-\u31E3\u31F0-\u321E\u3220-\u3247\u3250-\u32FE\u3300-\u4DBF\u4E00-\uA48C\uA490-\uA4C6\uA960-\uA97C\uAC00-\uD7A3\uD7B0-\uD7C6\uD7CB-\uD7FB\uF900-\uFAFF\uFE10-\uFE19\uFE30-\uFE52\uFE54-\uFE66\uFE68-\uFE6B\uFF01-\uFF60\uFFE0-\uFFE6]+)|[\v\f\uFEFF\u200B\u200C\u200D]+/g,
        setString: function (string){
            this._table = [];
            this._runs = this._genRuns(string);
            this._updateTable(0);
        },
        _updateTable: function (index){
            var table = this._table;
            this._runs.slice(index).reduce(function (offset, run, k){
                return (table[index + k] = offset + run.length);
            }, index ? this._table[index - 1] : 0);
        },
        spliceString: function (start, length, string){
            var end = start + length;
            var runs = this._runs;
            if (runs.length === 0) {
                this.setString(string);
                return;
            }

            var table = this._table;
            var left = 0;
            var right = table.length;
            var middle;
            while (left < right) {
                middle = (left + right) >> 1;
                if (start <= table[middle]) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            var startIndex = left;
            var startRun = runs[startIndex];
            var startOffset = startIndex ? start - table[startIndex - 1] : start;

            left = startIndex;
            right = table.length;
            while (left < right) {
                middle = (left + right) >> 1;
                if (end <= table[middle]) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            var endIndex = left;
            var endRun = runs[endIndex];
            var endOffset = endIndex ? end - table[endIndex - 1] : end;

            var tempRuns = this._genRuns(string,
                startRun, startOffset,
                endRun, endOffset);
            this._runs = runs.slice(0, startIndex).concat(
                tempRuns, runs.slice(endIndex + 1));
            this._table = table.slice(0, startIndex + tempRuns.length);
            this._updateTable(startIndex);
        },
        $getRuns: function (start, end){
            var runs = this._runs;
            if (runs.length === 0) {
                return [];
            }

            var table = this._table;
            var left = 0;
            var right = table.length;
            var middle;
            while (left < right) {
                middle = (left + right) >> 1;
                if (start <= table[middle]) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            var startIndex = left;
            var startRun = runs[startIndex];
            var startOffset = startIndex ? start - table[startIndex - 1] : start;

            left = startIndex;
            right = table.length;
            while (left < right) {
                middle = (left + right) >> 1;
                if (end <= table[middle]) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            var endIndex = left;
            var endRun = runs[endIndex];
            var endOffset = endIndex ? end - table[endIndex - 1] : end;

            if (startIndex === endIndex) {
                return [new Run(endOffset - startOffset, startRun.type)];
            }
            var ret = [];
            if (startRun && startOffset < startRun.length) {
                ret.push(new Run(startRun.length - startOffset, startRun.type));
            }
            ret = ret.concat(runs.slice(startIndex + 1, endIndex));
            if (endRun && endOffset !== 0) {
                ret.push(new Run(endOffset, endRun.type));
            }
            return ret;
        },
        _genRuns: function (string, startRun, startOffset, endRun, endOffset){
            var ret = [];
            if (startRun && startOffset > 0) {
                ret.push(new Run(startOffset, startRun.type));
            }
            var regex = this._regex;
            var match;
            var lastIndex = 0;
            regex.lastIndex = 0;
            while (match = regex.exec(string)) {
                var index = match.index;
                if (index > lastIndex) {
                    ret.push(new Run(index - lastIndex, _RUN_CHAR));
                }
                lastIndex = regex.lastIndex;
                ret.push(new Run(match[0].length, match[1] ? _RUN_TAB :
                    match[2] ? _RUN_CJK_CHAR : _RUN_CHAR));
            }
            if (lastIndex !== string.length) {
                ret.push(new Run(string.length - lastIndex, _RUN_CHAR));
            }
            if (endRun && endOffset < endRun.length) {
                ret.push(new Run(endRun.length - endOffset, endRun.type));
            }
            return ret;
        },
        computeColumn: function (start, length, column){
            var end = start + length;
            var runs = this._runs;
            if (runs.length === 0) {
                return column;
            }
            var table = this._table;
            var left = 0;
            var right = table.length;
            var middle;
            while (left < right) {
                middle = (left + right) >> 1;
                if (start <= table[middle]) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            var startIndex = left;
            var startRun = runs[startIndex];
            var startOffset = startIndex ? start - table[startIndex - 1] : start;

            left = startIndex;
            right = table.length;
            while (left < right) {
                middle = (left + right) >> 1;
                if (end <= table[middle]) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            var endIndex = left;
            var endRun = runs[endIndex];
            var endOffset = endIndex ? end - table[endIndex - 1] : end;
            if (startIndex === endIndex) {
                return this.computeRunColumn(new Run(endOffset - startOffset, startRun.type), column);
            }
            if (startRun) {
                column += this.computeRunColumn(new Run(startRun.length - startOffset, startRun.type), column);
            }
            var this_ = this;
            if (startIndex < endIndex) {
                column = runs.slice(startIndex + 1, endIndex).reduce(function (column, run){
                    return column + this_.computeRunColumn(run, column);
                }, column);
                if (endRun) {
                    column += this.computeRunColumn(new Run(endOffset, endRun.type), column);
                }
            }
            return column;
        },
        computeRunColumn: function (run, column){
            switch (run.type) {
            case _RUN_CHAR:
                return run.length;
            case _RUN_CJK_CHAR:
                return (run.length * 2);
            case _RUN_TAB:
                return run.length ? (run.length * this.tabSize - column % this.tabSize) : 0;
            }
            return 0;
        },
        computeColumnOffset: function (start, column, mode){
            var runs = this._runs;
            if (runs.length === 0) {
                return [start, column];
            }
            var table = this._table;
            var left = 0;
            var right = table.length;
            var middle;
            while (left < right) {
                middle = (left + right) >> 1;
                if (start <= table[middle]) {
                    right = middle;
                } else {
                    left = middle + 1;
                }
            }
            var runIndex = left;
            var run = runs[runIndex];
            var stepOffset = start;
            var runOffset = runIndex ? table[runIndex - 1] : 0;
            var stepColumn = 0;
            while (runOffset + run.length > stepOffset) {
                var runLength = runOffset + run.length - stepOffset;
                var runColumn = this.computeRunColumn(new Run(runLength, run.type), stepColumn);
                if (stepColumn + runColumn > column) {
                    break;
                }
                stepColumn += runColumn;
                stepOffset += runLength;
                runOffset += run.length;
                run = runs[++ runIndex];
                if (!run || stepColumn === column) {
                    return [stepOffset, stepColumn];
                }
            }
            var deltaOffset = 0;
            if (!run || run.type === _RUN_ZERO) {
                deltaOffset = 0;
            } else if (run.type === _RUN_TAB) {
                deltaOffset = Math.floor((column - stepColumn) / this.tabSize);
                stepColumn += deltaOffset * this.tabSize;
                deltaOffset += mode === 1 ? 1 :
                    mode === -1 ? 0 : column >= (stepColumn + stepColumn + runColumn) / 2 ? 1 : 0;
            } else {
                var fn = mode === 1 ? Math.ceil :
                    mode === -1 ? Math.floor : Math.round;
                var unitColumn = run.type === _RUN_CJK_CHAR ? 2 : 1;
                deltaOffset = fn.call(Math, (column - stepColumn) / unitColumn);
                stepColumn += deltaOffset * unitColumn;
            }
            return [stepOffset + deltaOffset, stepColumn];
        }
    };

    function Run(length, type){
        this.length = length;
        this.type = type;
    }

})();
